Packet networks such as the Internet carry large volume and variety of digital data traffic nowadays. Typically, different flows of traffic enter a network at a number of inlets, being further directed to a number of outlets, where a queue placed at the network outlet may receive data from several inlets. As long as the data rate into the queue, which is the combined incoming traffic from all flows directed to the queue, does not exceed the egress rate from the queue, the queue remains empty. The queue fills up when the incoming traffic exceeds an egress rate, and the purpose of the queue is to absorb such higher rates, which occur for short periods of time as a result of the statistical variations of the packet traffic in the network.
Packets are lost when the queue overflows. A simple method by which network congestion could be managed is to allow queues to overflow and rely on the network users to reduce their rate of traffic as a response to the loss of packets. Unfortunately, this approach to data flow management, typically used in so-called end-to-end protocols such as the commonly used Transmission Control Protocol (TCP), is not adequate to control network congestion fairly and efficiently.
A more advanced congestion control method is found in RED (Random Early Discard, also variously named Random Early Detection) in which packets are dropped randomly before the queue is full. Internet Engineering Task Force (IETF) document entitled RFC (Request For Comment) 2309 “Recommendations on Queue Management and Congestion Avoidance in the Internet” published in April 1998, provides a discussion of said undesirable effects, which happen during the network congestion, with regard to the TCP protocol, and a brief description of the RED method. In more detail, a simple RED method uses the concept of a drop probability, which is derived from the average queue fill level. When the average queue fill level is less than the lower threshold (minimum), the drop probability is considered to be zero. When the average queue fill level is higher than the upper threshold (maximum), the drop probability is considered to be one. When the average queue fill level is between the minimum and maximum, the drop probability is interpolated between 0 and 1. Packets arriving at the queue are dropped according to the drop probability.
The simple RED method as described above has a number of shortcomings, most notable of which is that the decisions in traffic management in RED are made without regard to the flow rate and/or characteristics, which causes unfairness of the decisions made for flows having different rates and characteristics.
Improvements and extensions to the simple RED method have been proposed, for example in an article by Dong Lin and Robert Morris, “Dynamics of Random Early Detection” published by MIT Lab for Computer Science, Parallel & Distributed Operating Systems Group at http://www.pdos.lcs.mit.edu/˜rtm/papers/fred.pdf, where FRED (Flow-based RED) method has been described; and in an article by Ulf Bodin et al., “Load-tolerant Differentiation with Active Queue Management” published in Computer Communications Review, a technical letter for SIGCOMM, in July 2000 at http://www.acm.org/sigcomm/ccr/archive/2000/july00/bodin.pdf, where WRED (Weighted RED) method has been described. In FRED, drop probabilities are maintained separately for all flows present in the queue, while WRED uses Internet Protocol (IP) precedence of each packet to modify the drop probability.
Yet another modification of the RED method is described in the U.S. Pat. No. 6,252,848 to Skirmont entitled “System performance in a data network through queue management based on ingress rate monitoring”, which uses ingress flow measurements and flow profiles to modify the drop probability.
All RED methods, including advanced derivatives thereof cited above, require increasingly complex computational power at each egress queue to evaluate the drop probability, which may not be acceptable in some situations. For example, in a network having multiple switches, where queues at the outlets of the switches require congestion management, multiple performing of RED or its modifications would result in the multiple performing of time consuming computational processing, which significantly increases the cost of a large network and may cause unnecessary delay in other operations of the system.
Therefore there is a need in industry for the development of such a system and method for traffic management in a packet network, which would avoid the above-mentioned drawbacks.